package zmatch

import (
	"strings"
)

var (
	ANY_CHAR     byte = '*' // 匹配所有字符
	ANY_ONE_CHAR byte = '?' // 匹配单个字符
)

func kmp(needle string, str string) int {
	next := getNext(needle)
	//fmt.Println(next)

	j := 0
	for i := 0; i < len(str); i++ {
		for j > 0 && str[i] != needle[j] &&
			needle[j] != ANY_ONE_CHAR { // 加上 ? 匹配任意字符
			j = next[j-1] + 1
		}
		if str[i] == needle[j] ||
			needle[j] == ANY_ONE_CHAR { // 加上 ? 匹配任意字符
			j++
		}
		if j == len(needle) {
			return i - j + 1
		}
	}
	return -1
}

func getNext(needle string) []int {
	var next = make([]int, len(needle))

	next[0] = -1
	k := -1
	for i := 1; i < len(needle); i++ {
		for k != -1 && needle[k+1] != needle[i] &&
			needle[k+1] != ANY_ONE_CHAR && needle[i] != ANY_ONE_CHAR { // 加上 ? 匹配任意字符
			k = next[k]
		}
		if needle[k+1] == needle[i] ||
			needle[k+1] == ANY_ONE_CHAR || needle[i] == ANY_ONE_CHAR { // 加上 ? 匹配任意字符
			k++
		}
		next[i] = k
	}
	return next
}

// 检测字串是否和模式匹配。
// 注意：仅支持 * 和 ? 匹配
func IsMatch(content, parttern string) bool {
	// todo: parttern * 号去重

	if len(content)*2+1 < len(parttern) || parttern == "" {
		return false
	}
	var tstr = content

	// 如果 parttern 不是以 * 结尾，结尾则要进行全匹配
	if pidx := len(parttern) - 1; parttern[pidx] != ANY_CHAR {
		cidx := len(tstr) - 1
		for {
			if pidx < 0 {
				return cidx < 0 // 没有 * 号的场景
			}
			if parttern[pidx] == ANY_CHAR {
				parttern = parttern[:pidx+1] //保留 * 字符
				tstr = tstr[:cidx+1]         // 当前的字符没有比对，所以要加回来
				break
			}

			if cidx < 0 || parttern[pidx] != tstr[cidx] && parttern[pidx] != ANY_ONE_CHAR {
				return false
			}

			pidx--
			cidx--
		}
	}

	// 如果 parttern 不是以 * 开头，开头则要进行全匹配
	if parttern[0] != ANY_CHAR {
		for idx := 0; ; idx++ {
			if idx >= len(parttern) { // 没有 * 字符
				return idx >= len(tstr)
			}
			if parttern[idx] == ANY_CHAR {
				parttern = parttern[idx:] //保留 * 字符
				tstr = tstr[idx:]         // 当前的字符没有比对，所以要加回来
				break
			}

			if idx >= len(tstr) || parttern[idx] != tstr[idx] && parttern[idx] != ANY_ONE_CHAR {
				return false
			}
		}
	}

	/*
		if len(parttern) == 1 { // 长度为 1，说明只是一个 * 字符
			if parttern[0] != ANY_CHAR {
				panic("bug!")
			}
			return true
		}
	*/

	parts := strings.Split(parttern, string(ANY_CHAR))
	//fmt.Println("parts:", parts, " len:", len(parts))
	for _, part := range parts {
		if part == "" {
			continue
		}
		if tstr == "" {
			return false
		}

		if idx := kmp(part, tstr); idx < 0 {
			return false
		} else {
			tstr = tstr[idx+len(part):]
		}
	}

	return true
}

/*
func main() {
	fmt.Println(isMatch("abc", "abc"))
	fmt.Println(isMatch("abc", "abc*"))
	fmt.Println(isMatch("abc", "*abc"))
	fmt.Println(isMatch("abc", "a*b*c"))
	fmt.Println(isMatch("abc", "a?c"))
	fmt.Println(isMatch("abc", "a??c"))
	fmt.Println(isMatch("abc.com", "*.abc.com"))
}
*/
